/*
 * @lc app=leetcode.cn id=498 lang=typescript
 *
 * [498] 对角线遍历
 */

// @lc code=start
function findDiagonalOrder(mat: number[][]): number[] {
  const m = mat.length;
  const n = mat[0].length;
  const ans = new Array(m * n);
  // 对角线数量
  const diagonals = m + n - 1;
  // 结果数组的索引
  let idx = 0;
  for (let i = 0; i < diagonals; i++) {
    if (i % 2 === 0) {
      // 对角线为偶数时，左上往右上遍历
      let x = i < m ? i : m - 1;
      let y = i < m ? 0 : i - m + 1;
      while (x >= 0 && y < n) {
        ans[idx++] = mat[x--][y++];
      }
    } else {
      // 对角线为奇数时，右上往左下遍历
      let x = i < n ? 0 : i - n + 1;
      let y = i < n ? i : n - 1;
      while (x < m && y >= 0) {
        ans[idx++] = mat[x++][y--];
      }
    }
  }

  return ans;
}
// @lc code=end
